nums = [-2,1,-3,4,-1,2,1,-5,4]
# nums=[1]
# nums=[-1]
# nums=[-100000]
def maxSubArray(nums):
    numsLen=len(nums)
    dp=[0 for _ in range(numsLen)]
    #先判断第一个位置
    dp[0]=nums[0]
    #判断剩余位置
    for i in range(1,numsLen):
        dp[i]=max(nums[i],dp[i-1]+nums[i])
    return max(dp)


def maxSubArray1(nums):
    numsLen=len(nums)
    dp=[0 for _ in range(2)]
    #先判断第一个位置
    dp[0]=nums[0]
    maxValue=dp[0]
    #判断剩余位置
    for i in range(1,numsLen):
        dp[i&1]=max(nums[i],dp[(i-1)&1]+nums[i])
        if maxValue<dp[i&1]:
            maxValue=dp[i&1]
    return maxValue

print(maxSubArray(nums))